<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 递增字符串（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>定义字符串完全由 ‘A’ 和 ‘B’组成&#xff0c;当然也可以全是’A’或全是’B’。如果字符串从前往后都是以字典序排列的&#xff0c;那么我们称之为严格递增字符串。<br /> 给出一个字符串s&#xff0c;允许修改字符串中的任意字符&#xff0c;即可以将任何的’A’修改成’B’&#xff0c;也可以将任何的’B’修改成’A’&#xff0c;<br /> 求可以使s满足严格递增的最小修改次数。</p> 
<p>0 &lt; s的长度 &lt; 100000。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入一个字符串&#xff1a; “AABBA”</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出&#xff1a;1</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">AABBA</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">修改最后一位得到AABBB。</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>新增一个用例&#xff1a;</p> 
<blockquote> 
 <p>AAA<span style="color:#fe2c24;">B</span>AAABBBB<span style="color:#fe2c24;">A</span>BB</p> 
</blockquote> 
<p>该用例只需要修改两次。</p> 
<p></p> 
<p>我的解题思路如下&#xff1a;</p> 
<p>首先&#xff0c;我们需要记录字符串长度为total&#xff0c;然后统计字符串中A的数量&#xff0c;记为A。</p> 
<p>然后用动态规划&#xff0c;即定义一个dp数组&#xff0c;dp[i]的含义是 [0,i]闭区间内有多少个A。</p> 
<p>统计好后&#xff0c;我们可以假设将 0 ~ i 闭区间内全部变成A&#xff0c;需要修改多少次&#xff1f;</p> 
<blockquote> 
 <p>0~i闭区间内理论会有 i&#43;1 个A&#xff0c;而目前有dp[i] 个A&#xff0c;因此需要修改 i &#43; 1 - dp[i] 次。</p> 
</blockquote> 
<p>接着考虑将 i&#43;1 ~ str.length-1 区间内全部变成B&#xff0c;需要修改多少次&#xff1f;</p> 
<blockquote> 
 <p>dp[i]表示 0~i闭区间内A的数量&#xff0c;那么 i&#43;1~str.length-1 区间内A的数量&#61; A - dp[i]</p> 
 <p>因此需要修改A - dp[i]次</p> 
</blockquote> 
<p>因此&#xff0c;一共需要修改 i &#43; 1 - dp[i] &#43; A - dp[i] 次</p> 
<p></p> 
<p>我们从 0 ~ str.length-1 遍历出每一个 i 带入上面公式&#xff0c;保留最小的结果&#xff0c;就是题解。</p> 
<p></p> 
<p>另外&#xff0c;本题0 &lt; s的长度 &lt; 100000&#xff0c;如果使用dp数组的话&#xff0c;最坏需要定义一个100000长度的数组&#xff0c;这是有可能爆内存的&#xff0c;因此&#xff0c;下面代码中我不是dp数组&#xff0c;直接使用leftA变量。</p> 
<p></p> 
<p>补充一下&#xff1a;上面逻辑遗漏考虑两个分界线位置&#xff1a;</p> 
<p><img alt="" height="84" src="https://img-blog.csdnimg.cn/b916abdb3fd74444be70a381774ab63d.png" width="383" /></p> 
<p>如上图所示&#xff0c;分别是-1索引位置和n索引位置&#xff0c;即上图两个绿色箭头位置。</p> 
<p>前面逻辑&#xff0c;只考虑分界线位置在数组索引的0~n-1&#xff0c;因此当用例如下时&#xff1a;</p> 
<p>BBABB</p> 
<p>使用上面逻辑会产生问题。</p> 
<p>此时&#xff0c;我们应该记录将字符串全部修改为A的次数&#xff0c;和全部修改为B的次数&#xff0c;即上面两个绿色箭头分界线。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  console.log(getResult(line));
});

function getResult(str) {
  const total &#61; str.length;
  const A &#61; str.replaceAll(&#34;B&#34;, &#34;&#34;).length; // 字符串str中共有多少个A

  // 如果全B或全A&#xff0c;则直接返回0
  if (A &#61;&#61; 0 || A &#61;&#61; total) return 0;

  // 修改为全A或者全B的次数取最小值
  let ans &#61; Math.min(A, total - A);

  let leftA &#61; 0;
  for (let i &#61; 0; i &lt; total; i&#43;&#43;) {
    if (str[i] &#61;&#61; &#34;A&#34;) leftA&#43;&#43;;
    ans &#61; Math.min(i &#43; 1 - leftA &#43; A - leftA, ans);
  }

  return ans;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String str &#61; sc.next();
    System.out.println(getResult(str));
  }

  public static int getResult(String str) {
    int total &#61; str.length();
    int A &#61; str.replaceAll(&#34;B&#34;, &#34;&#34;).length(); // 字符串str中共有多少个A

    // 如果全B或全A&#xff0c;则直接返回0
    if (A &#61;&#61; 0 || A &#61;&#61; total) return 0;

    // 修改为全A或者全B的次数取最小值
    int ans &#61; Math.min(A, total - A);

    int leftA &#61; 0;
    for (int i &#61; 0; i &lt; total; i&#43;&#43;) {
      if (str.charAt(i) &#61;&#61; &#39;A&#39;) leftA&#43;&#43;;
      ans &#61; Math.min(i &#43; 1 - leftA &#43; A - leftA, ans);
    }

    return ans;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
s &#61; input()


# 算法入口
def getResult(s):
    total &#61; len(s)
    A &#61; len(s.replace(&#34;B&#34;, &#34;&#34;))  # 字符串str中共有多少个A

    # 如果全B或全A&#xff0c;则直接返回0
    if A &#61;&#61; 0 or A &#61;&#61; total:
        return 0

    # 修改为全A或者全B的次数取最小值
    ans &#61; min(A, total - A)

    leftA &#61; 0
    for i in range(total):
        if s[i] &#61;&#61; &#39;A&#39;:
            leftA &#43;&#61; 1

        ans &#61; min(i &#43; 1 - leftA &#43; A - leftA, ans)

    return ans


# 算法调用
print(getResult(s))
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>